//
// Created by liushuai on 12/19/19.
//
#include <unordered_map>
static std::unordered_map<int, long> cache;
long fib(int n) {
  if (cache.count(n)) return cache.at(n);
  int result;
  if (n < 2)
    result = n;
  else
    result = fib(n - 1) + fib(n - 2);
  cache[n] = result;
  return result;
}

long fib1(int n) {
  if (0 == n || 1 == n)

    return n;

  else {
    int cache[2] = {0, 1};
    for (int i = 2; i <= n; i++) {
      int temp = cache[0] + cache[1];
      cache[0] = cache[1];
      cache[1] = temp;
    }
    return cache[1];
  }
}
